public class LeetCode611_Number_Triangles {
    public int triangleNumber(int[] nums) {
        shellSort(nums);
        // for (int i = 0; i < nums.length; i++) {
        //     for (int j = i + 1; j < nums.length; j++) {
        //         if (nums[i] > nums[j]) {
        //             swap(nums, i, j);
        //         }
        //     }
        // }
        int p = nums.length - 1;
        int count = 0;
        while (p > 1) {
            int left = 0;
            int right = p - 1;
            while (left < right) {
                if (nums[left] + nums[right] > nums[p]) {
                    count += (right - left);
                    right--;
                } else {
                    left++;
                }
            }
            p--;
        }

        return count;
    }

    public void shellSort(int[] arr) {
        int gap = 5;
        while (gap >= 1) {
            for (int i = gap; i < arr.length; i++) {
                int temp = arr[i];
                int j = i - gap;
                for (; j >= 0; j -= gap) {
                    if (arr[j] > temp) {
                        arr[j + gap] = arr[j];
                    } else {
                        arr[j + gap] = temp;
                        break;
                    }
                }
                if (j < 0) {
                    arr[j + gap] = temp;
                }
            }
            gap /= 2;
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
